
using Nirvana;
using System.Collections;
using System.Collections.Generic;
using UnityEngine;


public static class PoissonDiskSampling
{
    public struct PoissonDiskSamplingData
    {
        public Vector3 pos;
        public float raduis;
    }

    private static List<Vector3> points = new List<Vector3>();
    private static List<Vector3> spawnPoints = new List<Vector3>();

    /// <summary>
    /// 泊松盘采样算法：均匀随机分布
    /// </summary>
    /// <param name="radius">个体间距</param>
    /// <param name="sampleRegionSize">采样空间</param>
    /// <param name="findNum">数量</param>
    /// <param name="numSamplesBeforeRejection">默认32次最优</param>
    /// <returns></returns>

    public static List<Vector3> GeneratePoints(float radius, Vector2 sampleRegionSize, int findNum, int numSamplesBeforeRejection = 32)
    {
        //创建一个网格，使每个单元格最多包含一个采样圆盘点
        //那么单元格的对角线长度应等于采样圆盘的半径R
        //假设整个区域由N*N个同样大学的方格组成，则一个方格的对角线长度正好是r，即网格的边长就是: r/sqrt(2)
        float cellSize = radius / Mathf.Sqrt(2);
        Vector3[,] grid = new Vector3[Mathf.CeilToInt(sampleRegionSize.x / cellSize), Mathf.CeilToInt(sampleRegionSize.y / cellSize)];
        
        points.Clear();
        spawnPoints.Clear();
        //var fristPoint = new Vector3(sampleRegionSize.x / 2f, 0f, sampleRegionSize.y / 2f);
        //随机区域取一起始点
        var fristPoint = new Vector3(Random.Range(sampleRegionSize.x *0.2f, sampleRegionSize.x * 0.8f),0,Random.Range(sampleRegionSize.y * 0.2f, sampleRegionSize.y * 0.8f));

        spawnPoints.Add(fristPoint);
        points.Add(fristPoint);

        var fristCellPoint = ImageToGrid(fristPoint, cellSize);
        grid[fristCellPoint.x,fristCellPoint.y] = fristPoint;


        while (spawnPoints.Count > 0)
        {
            int spawnIndex = Random.Range(0, spawnPoints.Count);
            Vector3 spawnCenter = spawnPoints[spawnIndex];
            bool candidateAccepted = false;
            for (int i = 0; i < numSamplesBeforeRejection; i++)
            {
                var newPoint = GenerateRandom2DPointAround(spawnCenter, radius);
                
                if (!inNeighbourhood(grid,newPoint, radius, cellSize, sampleRegionSize))
                {
                    //当前节点周围没有邻居节点，则保存
                    points.Add(newPoint);
                    spawnPoints.Add(newPoint);
               
                    grid[Mathf.RoundToInt(newPoint.x / cellSize), Mathf.RoundToInt(newPoint.z / cellSize)] = newPoint; //记录当前ceil占位的节点
                    candidateAccepted = true;
                    if (points.Count >= findNum)
                    {
                        return points;
                    }
                    break;
                }
            }

            if (!candidateAccepted)
            {
                spawnPoints.RemoveAt(spawnIndex);
            }
        }
        return points;
    }
    private static Vector2Int ImageToGrid(Vector3 point, float cellSize)
    {
        return new Vector2Int(Mathf.CeilToInt(point.x / cellSize),Mathf.CeilToInt(point.z / cellSize));
    }
    /// <summary>
    /// 检测当前点周围3格范围内是否有邻居节点。
    /// </summary>
    /// <param name="grid"></param>
    /// <param name="point"></param>
    /// <param name="mindist"></param>
    /// <param name="cellSize"></param>
    /// <param name="sampleRegionSize"></param>
    /// <returns></returns>
    private static bool inNeighbourhood(Vector3[,] grid,Vector3 point,float mindist,float cellSize, Vector2 sampleRegionSize)
    {
        
        if (point.x - mindist >= 0f && point.x + mindist < sampleRegionSize.x && point.z - mindist >= 0f && point.z + mindist < sampleRegionSize.y)
        {
            int cellX = Mathf.RoundToInt(point.x / cellSize);
            int cellZ = Mathf.RoundToInt(point.z / cellSize);
            int searchStartX = Mathf.Max(0, cellX - 3);
            int searchEndX = Mathf.Min(cellX + 3, grid.GetLength(0) - 1);
            int searchStartZ = Mathf.Max(0, cellZ - 3);
            int searchEndZ = Mathf.Min(cellZ + 3, grid.GetLength(1) - 1);
            float dist = mindist * 2;
            //查询当前点周围3格范围内是否有邻居节点。
            for (int x = searchStartX; x <= searchEndX; x++)
            {
                for (int z = searchStartZ; z <= searchEndZ; z++)
                {
                    var cell = grid[x, z];
                    if (cell == null) continue;
                    
                    //优化，根据三角定律：2边之和大于第三边，假如2点间距离小于2点构成的三角边，说明距离接近，不用判断了
                    if (cell.x + point.x + cell.z + point.z < dist) continue;
                    if (Vector3.Distance(cell, point) < dist) return true; //检测相距邻居节点间距离是否小于直径
                }
            }

            return false;
        }

        return true;
    }

    /// <summary>
    /// 获取一个随机方向的坐标点
    /// </summary>
    /// <param name="point"></param>
    /// <param name="radius"></param>
    /// <returns></returns>
    private static Vector3 GenerateRandomPointAround(Vector3 point,float radius)
    {
        float angle = Random.value * Mathf.PI * 2f;
        Vector3 dir = new Vector3(Mathf.Sin(angle), 0f, Mathf.Cos(angle));
        Vector3 newPoint = point + dir.normalized * Random.Range(2f, 3f) * radius; //两圆中心点距离最少2~3个半径
        return newPoint;
    }
    private static Vector3 GenerateRandom2DPointAround(Vector3 point, float radius)
    {
        float angle = Random.value * Mathf.PI * 2f;
        float dirRange = Random.Range(2f, 3f);

        float newX = point.x + radius * Mathf.Sin(angle) * dirRange;
        float newY = point.z + radius * Mathf.Cos(angle) * dirRange;
        return new Vector3(newX, 0, newY);
    }
    /// <summary>
    /// 获取一个3D坐标
    /// </summary>
    /// <param name="point"></param>
    /// <param name="radius"></param>
    /// <returns></returns>
    private static Vector3 GenerateRandom3DPointAround(Vector3 point, float radius)
    {
        float angle1 = Random.value * Mathf.PI * 2f;
        float angle2 = Random.value * Mathf.PI * 2f;
        float dirRange = Random.Range(2f, 3f);

        float newX = point.x + radius * Mathf.Cos(angle1) * Mathf.Sin(angle2) * dirRange;
        float newY = point.y + radius * Mathf.Sin(angle1) * Mathf.Cos(angle2) * dirRange;
        float newZ = point.z + radius * Mathf.Cos(angle2) * dirRange;
        return new Vector3(newX,newY,newZ);
    }


    /// <summary>
    /// 泊松样本集的一个重要变化是点之间的最小距离不是恒定的，而是在整个图像中变化的。在这种变化中，我们为算法提供灰度图像，该图像用于调节点之间的最小距离。
    /// 比如：一张地图，有的山区需求矿点密集，河流，城镇区域需要矿点稀疏
    /// </summary>
    /// <param name="point"></param>
    /// <param name="minDistance"></param>
    /// <param name="maxDistance"></param>
    /// <param name="texture"></param>
    /// <returns></returns>
    private static Vector3 GenerateRandomPointAroundDensity(Vector3 point,float minDistance,float maxDistance,Texture2D texture)
    {
        Color color = texture.GetPixel((int)point.x, (int)point.z);
        float angle = Random.value * Mathf.PI * 2f;
        float newMinDistance = minDistance + (maxDistance - minDistance) * (1.0f - (float)color.a / 255f);
        float dirRange = Random.Range(2f, 3f);
        float newX = point.x + newMinDistance * Mathf.Sin(angle) * dirRange;
        float newY = point.z + newMinDistance * Mathf.Cos(angle) * dirRange;

        return new Vector3(newX, 0, newY);
    }
    private static Vector3 GenerateRandomPointAroundDensity2(Vector3 point, float minDistance, float maxDistance, float grey)
    {
        float angle = Random.value * Mathf.PI * 2f;
        float newMinDistance = minDistance + (maxDistance - minDistance) * grey;
        float dirRange = Random.Range(2f, 3f);
        float newX = point.x + newMinDistance * Mathf.Sin(angle) * dirRange;
        float newY = point.z + newMinDistance * Mathf.Cos(angle) * dirRange;

        return new Vector3(newX, 0, newY);
    }


    private static List<PoissonDiskSamplingData> RandomPoints = new List<PoissonDiskSamplingData>();
    private static List<PoissonDiskSamplingData> RandomSpawnPoints = new List<PoissonDiskSamplingData>();
    private static bool inNeighbourhood(List<PoissonDiskSamplingData> grid, PoissonDiskSamplingData point,  Vector2 sampleRegionSize)
    {

        if (point.pos.x - point.raduis >= 0f && point.pos.x + point. raduis < sampleRegionSize.x && point.pos.z - point.raduis >= 0f && point.pos.z + point.raduis < sampleRegionSize.y)
        {

            for(int i =0; i < grid.Count; i++)
            {
                var cell = grid[i];
                float dist = (cell.raduis + point.raduis);
                //优化，根据三角定律：2边之和大于第三边，假如2点间距离小于2点构成的三角边，说明距离接近，不用判断了
                if (cell.pos.x + point.pos.x + cell.pos.z + point.pos.z < dist) continue; 
                if (Vector3.Distance(cell.pos, point.pos) < dist) return true; //检测相距邻居节点间距离是否小于直径
            }

            return false;
        }

        return true;
    }
    /// <summary>
    /// 随机半径采样
    /// </summary>
    /// <param name="randomRadius"></param>
    /// <param name="sampleRegionSize"></param>
    /// <param name="findNum"></param>
    /// <param name="numSamplesBeforeRejection"></param>
    /// <returns></returns>
    public static List<PoissonDiskSamplingData> GenerateRandomRaduisPoints(Vector2 randomRadius, Vector2 sampleRegionSize, int findNum, int numSamplesBeforeRejection = 32)
    {

        float radius = 0;

        RandomPoints.Clear();
        RandomSpawnPoints.Clear();
        var startPos = new PoissonDiskSamplingData();
        startPos.pos = new Vector3(sampleRegionSize.x / 2f, 0f, sampleRegionSize.y / 2f);
        startPos.raduis = Random.Range(randomRadius.x, randomRadius.y);
        RandomSpawnPoints.Add(startPos); //起点从中间开始扩散
        RandomPoints.Add(startPos);

        while (RandomSpawnPoints.Count > 0)
        {
            int spawnIndex = Random.Range(0, RandomSpawnPoints.Count);
            var spawnCenter = RandomSpawnPoints[spawnIndex];
            bool candidateAccepted = false;
            for (int i = 0; i < numSamplesBeforeRejection; i++)
            {
                radius = Random.Range(randomRadius.x, randomRadius.y);
                float angle = Random.value * Mathf.PI * 2f;
                Vector3 dir = new Vector3(Mathf.Sin(angle), 0f, Mathf.Cos(angle));
                Vector3 newPoint = spawnCenter.pos + dir.normalized * (spawnCenter.raduis + radius +Random.Range(1f, 3f));

                var newPointData = new PoissonDiskSamplingData();
                newPointData.pos = newPoint;
                newPointData.raduis = radius;

                if (!inNeighbourhood(RandomPoints, newPointData, sampleRegionSize))
                {
                    //当前节点周围没有邻居节点，则保存
                    RandomPoints.Add(newPointData);
                    RandomSpawnPoints.Add(newPointData);

                    candidateAccepted = true;
                    if (RandomPoints.Count >= findNum)
                    {
                        return RandomPoints;
                    }
                    break;
                }
            }

            if (!candidateAccepted)
            {
                RandomSpawnPoints.RemoveAt(spawnIndex);
            }
        }
     

        return RandomPoints;
    }

    /// <summary>
    /// 获取一个正方形范围内平均分布点
    /// </summary>
    /// <param name="point"></param>
    /// <param name="radius"></param>
    /// <returns></returns>
    public static List<Vector3> GenerateEvenlyDistributedPoint(Vector3 center, int num, float radius)
    {
        points.Clear();
        int ecurEemyCount = 1;
        const float phi2 = 1.3247179572447458f;
        const float a1 = 1.0f / (phi2 * phi2);
        const float a2 = 1.0f / phi2;
        for (int i = 0; i < num; i++)
        {
            float x = (0.5f + a2 * ecurEemyCount) % 1;
            float y = (0.5f + a1 * ecurEemyCount) % 1;
            // 将 x 和 y 从 [0, 1) 范围转换到 [-1, 1) 范围
            x = 2 * (x - 0.5f);
            y = 2 * (y - 0.5f);

            x = x * radius + center.x;
            y = y * radius + center.y;

            ecurEemyCount++;

            points.Add(new Vector3(x,0,y));
        }
        return points;
    }
    /// <summary>
    /// 获取一个圆环内平均分布点
    /// </summary>
    /// <returns></returns>
    public static List<Vector3> GenerateEvenlyDistributedPoint(Vector3 center, int num, float radiusMax,float radiusMin)
    {
        points.Clear();
        int ecurEemyCount = 1;
        const float phi2 = 1.3247179572447458f;
        const float a1 = 1.0f / (phi2 * phi2);
        const float a2 = 1.0f / phi2;
        for (int i = 0; i < num; i++)
        {
            float x = (0.5f + a2 * ecurEemyCount) % 1;
            float y = (0.5f + a1 * ecurEemyCount) % 1;
            // 将 x 和 y 从 [0, 1) 范围转换到 [-1, 1) 范围
            x = 2 * (x - 0.5f);
            y = 2 * (y - 0.5f);

            // 计算极坐标中的半径 r 和角度 theta
            float r = (float)Mathf.Sqrt(x * x + y * y);
            float theta = (float)Mathf.Atan2(y, x);

            // 将半径 r 从 [0, 1] 范围映射到 [rmin, rmax] 范围
            r = radiusMin + r * (radiusMax - radiusMin);

            // 将极坐标转换为直角坐标
            x = r * (float)Mathf.Cos(theta);
            y = r * (float)Mathf.Sin(theta);


            x += center.x;
            y += center.y;

            ecurEemyCount++;

            points.Add(new Vector3(x, 0, y));
        }
        return points;
    }

    /// <summary>
    /// 二维向日葵螺旋算法:圆盘内，均匀分布点数，数量越多，圆形越像
    /// </summary>
    /// <param name="num">点数</param>
    /// <param name="radius">圆半径</param>
    public static List<Vector3> GenerateCirclePoints(int num, float radius)
    {
        points.Clear();
        float f = Mathf.Sqrt(5);
        for (int i = 0; i < num; i++)
        {
            float t = i + 0.5f;
            //径向间隔点,来计算第i个点应该离圆心多远。
            float r = Mathf.Sqrt(t / num); //屏蔽，使用半径r，则是个圆环，开启，则是个均匀分布的圆
            //每个圆环上的点应该相隔多少角度
            float theta = Mathf.PI * (1 + f) * t;
            // float theta = Mathf.PI * (3- Mathf.Sqrt(5)) * t;
            var pos = new Vector3(r * Mathf.Cos(theta) * radius, 0, r * Mathf.Sin(theta) * radius);
            points.Add(pos);
        }
        return points;
    }
    /// <summary>
    /// 获取矩阵
    /// </summary>
    /// <param name="columns">固定列数</param>
    /// <param name="num">点数数量</param>
    /// <param name="xOff">x轴间距</param>
    /// <param name="yOff">y轴间距</param>
    /// <returns></returns>
    public static List<Vector3> GenerateMatrixPoints(int columns, int num, float xOff, float yOff)
    {
        points.Clear();
        for (int i = 0; i < num; i++)
        {
            int row = i / columns;
            int col = i % columns;

            var pos = new Vector3(col * xOff, 0, row * yOff);
            points.Add(pos);
        }

        return points;
    }
    /// <summary>
    /// 三角形阵列
    /// </summary>
    /// <param name="totalCount"></param>
    /// <param name="xOff"></param>
    /// <param name="yOff"></param>
    /// <param name="angle">上下左右方向：0:右,90：上,180：左,270：下,其它度数任意角度</param>
    /// <returns></returns>
    public static List<Vector3> GenerateTrianglePoints(int totalCount, float xOff, float yOff, float angle)
    {
        points.Clear();

        float spaceX = xOff;
        float spaceZ = yOff;
        int curCount = 0;
        int index = 0;
        //三角形规则：每行的行数等于当前行的点数：第2行2个点，第3行3个点，4行4点
        //各点错落排开
        while (curCount < totalCount)
        {
            index++;
            float width = spaceX * (index - 1); //宽
            float halfWidth = width * 0.5f;
            for (int i = 0; i < index; i++)
            {
                //计算本地坐标偏移
                Vector3 offsetpos = new Vector3((index - 1) * spaceX, 0, (i * spaceZ - halfWidth));
                points.Add(offsetpos);
                curCount++;

                if (curCount == totalCount) break;
            }
        }

        //坐标旋转公式
        if (angle > 0)
        {
            for (int i = 0; i < points.Count; i++)
            {
                var pos = points[i];
                float x = Mathf.Cos(angle * Mathf.Deg2Rad) * pos.x - Mathf.Sin(angle * Mathf.Deg2Rad) * pos.z;
                float z = Mathf.Cos(angle * Mathf.Deg2Rad) * pos.z + Mathf.Sin(angle * Mathf.Deg2Rad) * pos.x;
                points[i] = new Vector3(x, 0, z);
            }
        }

        return points;
    }

    /// <summary>
    /// 创建多组带方向的雁列式阵型: 人字型
    /// <param name="angle">上下左右方向：0:右,90：上,180：左,270：下,其它度数任意角度</param>
    /// </summary>
    public static List<Vector3> GenerateEchelonPoints(int num, int onegroupnum, float radius, float angle)
    {
        points.Clear();
        int group = num / onegroupnum;
        int remaning = num % onegroupnum;
        if (group > 0)
        {
            for (int i = 0; i < group; i++)
            {
                var list = GenerateOneEchelonPoints(onegroupnum, radius, radius);
                for (int j = 0; j < list.Count; j++)
                {
                    var pos = list[j];
                    pos = new Vector3(pos.x + radius * (i + 1), pos.y, pos.z);
                    points.Add(pos);
                }
            }
        }

        if (remaning > 0)
        {
            var list = GenerateOneEchelonPoints(remaning, radius, radius);
            for (int j = 0; j < list.Count; j++)
            {
                var pos = list[j];
                pos = new Vector3(pos.x + radius * (group + 1), pos.y, pos.z);
                points.Add(pos);
            }
        }

        //坐标旋转公式
        if (angle > 0)
        {
            for (int i = 0; i < points.Count; i++)
            {
                var pos = points[i];
                float x = Mathf.Cos(angle * Mathf.Deg2Rad) * pos.x - Mathf.Sin(angle * Mathf.Deg2Rad) * pos.z;
                float z = Mathf.Cos(angle * Mathf.Deg2Rad) * pos.z + Mathf.Sin(angle * Mathf.Deg2Rad) * pos.x;
                points[i] = new Vector3(x, 0, z);
            }
        }

        return points;
    }

    /// <summary>
    /// 创建一队雁列式阵型: 人字型,默认箭头朝左
    /// </summary>
    /// <param name="count"></param>
    /// <param name="xOff"></param>
    /// <param name="yOff"></param>
    /// <returns></returns>
    public static List<Vector3> GenerateOneEchelonPoints(int count, float xOff, float yOff)
    {
        spawnPoints.Clear();

        float spaceX = xOff;
        float spaceZ = yOff;
        float width = spaceX * (count - 1); //宽
        float height = spaceZ * (count - 1);//高
        float halfWidth = width * 0.5f;
        float halfHeight = height * 0.5f;

        int num2 = count / 2;
        int signZ = 1, signX = 1;

        //直线中心划分等点，两边点距离中心点越远，距离越大，0:和count-1,是左右两边尾点，距离中点越大
        for (int i = 0; i < count; i++)
        {
            //if (i < num2) signZ = -1;
            //else signZ = 1;

            if (i < num2) signX = -1;
            else signX = 1;

            //计算本地坐标偏移
            Vector3 offsetpos = new Vector3(signX * (i * spaceX - halfWidth), 0f, signZ * (i * spaceZ - halfHeight));

            spawnPoints.Add(offsetpos);
        }

        return spawnPoints;
    }

 

}